package com.leet.code.simple_array;

import java.util.Arrays;

/**
 * @description:
 * @author: WYG
 * @time: 2020/12/17 14:43
 */

public class NumEquivDominoPairs {
    public int BestNumEquivDominoPairs(int[][] dominoes) {
        //根据多米诺骨牌的规律可以得出:
        //多米诺骨牌的两个值中较大者*10+较小者的结果最大为99
        //而且如果根据对应的规则求出的值结果相同,那么这两个多米诺骨牌一定相同
        //通过存储这个计算结果的个数可以得出到底有多少多米诺骨牌相等
        //再通过排列组合可以求出等价的多米诺骨牌的数量

        //创建数组存储多米诺骨牌中相等的多米诺骨牌的数量
        int[] nums = new int[100];
        int res = 0;
        for (int i = 0; i < dominoes.length; i++) {
            int x = dominoes[i][0];
            int y = dominoes[i][1];
            //多米诺骨牌中的max*10+min;所得结果如果一样那么这两个多米诺骨牌就等价,那么对应的数组值就+1
            int num = x > y ? x * 10 + y : y * 10 + x;
            nums[num]++;
        }
        //我们要求的是(i,j)的数量,(i,j)和(j,i)不同,所以最终的结果为相同多米诺骨牌可以排列为几种组合,也就是x*(x-1)/2
        for (int i = 0; i < 100; i++) {
            res += nums[i] * (nums[i] - 1) / 2;
        }
        return res;
    }

    public int SecondNumEquivDominoPairs(int[][] dominoes) {
        int ans = 0;
        int[] cp = new int[100];
        for(int[] arr:dominoes){
            Arrays.sort(arr);
            ans+=cp[arr[0]*10+arr[1]]++;
        }
        return ans;
    }



    /**
     * 时间复杂度太高
     * @param dominoes
     * @return
     */
    public int numEquivDominoPairs(int[][] dominoes) {
        int res = 0;
        int row = dominoes.length;
        for (int i = 0; i < row; i++) {
            for (int j = i + 1; j < row; j++) {
                if (isEqual(dominoes[i],dominoes[j])) {
                    res++;
                }
            }
        }
        return res;
    }

    public boolean isEqual(int[] from, int[] to) {
        if (from[0] == to[0] && from[1] == to[1]) {
            return true;
        }
        if (from[0] == to[1] && from[1] == to[0]) {
            return true;
        }
        return false;
    }
}
